package leetcode_2401_2500;

import java.util.*;

public class LeeCode_2454 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(secondGreaterElement(new int[]{2, 4, 0, 9, 6})));
    }
    private static int[] secondGreaterElement(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
        for (int i = 0; i < n; i++) {
            List<int[]> tmp = new ArrayList<>();
            while (!queue.isEmpty() && queue.peek()[1] < nums[i]){
                int[] p = queue.poll();
                if (p[2] == 0){
                    p[2]++;
                    tmp.add(p);
                }else {
                    int index = p[0];
                    ans[index] = nums[i];
                }
            }
            queue.addAll(tmp);
            queue.add(new int[]{i, nums[i], 0});
        }
        return ans;
    }
}
